#include<iostream>
#include<stdbool.h>

namespace du {
	template<class T>
	struct list_node {
		list_node* _next;
		list_node* _prev;
		T _val;
		list_node(const T& val = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};
	
	template<class T >
	class list_iterator {
	private:
		typedef list_node<T> Node;
		Node* _node;
	public:
		list_iterator(Node* node)
			:_node(node)
		{}

		T& operator*()
		{
			return _node->_val;
		}

		list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		list_iterator<T>& operator++(int)
		{
			list_iterator tem(*this);
			_node = _node->_next;
			return tem;
		}

		bool operator!=(const list_iterator<T>& it)
		{
			return _node != it._node;
		}

		bool operator==(const list_iterator<T>& it)
		{
			return _node == it._node;
		}
	};

	template<class T>
	class list {
	private:
		typedef list_node<T> Node;
		Node* _head;
	public:
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			Node* push = new Node(x);
			push->_next = _head;
			push->_prev = _head->_prev;
			_head->_prev->_next = push;
			_head->_prev = push;
		}

		typedef list_iterator<T> iterator;
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return (iterator)_head;
		}

	};

}